\documentclass{article}%

\usepackage[left=1in,right=1in,top=1.2in,bottom=1.5in]{geometry}
\usepackage[T1]{fontenc}
\usepackage[fulloldstylenums]{kpfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage[bookmarks]{hyperref}

\pdfpagewidth 8.5in
\pdfpageheight 11.0in
\setlength{\parindent}{0pt}

\title{COMP 303 - Software Development}
\author{Gary Roumanis, Andrew Sutcliffe, Shen Chen Xu}

\begin{document}

\maketitle

\begin{description}
  \item[Changes]\hfill\\
    We introduced an abstract class \textsf{AIPlayer} to represent an AI
    player, which is extended by the subclasses \textsf{RandomPlayer},
    \textsf{HeuristicPlayer}, \textsf{CheatPlayer} and
    \textsf{MonteCarloPlayer}. The \textsf{HeuristicPlayer} and
    \textsf{CheatPlayer} make use of a new class \textsf{MoveOrderer} for
    evaluating available moves. Minor changes were made in the \textsf{Board}
    class to allow AI playing.
    
    The GUI was redesigned as it was cluttered by more and more buttons. A menu
    system is introduced via the class \textsf{MenuManager} to clean up the
    interface and corresponding changes are made in the \textsf{Viewer} class.
    The undo-redo functionality can be found in the `Edit' menu and the hint
    mode and AI playing can be found in the `Help' menu. All other
    functionalities are in the `File' menu.

  \item[The AI Players]\hfill\\
    As its name suggests, the random AI player plays randomly by choosing a move
    out of all possibles moves.

    The heuristic player improves over the random AI by selecting a move using
    heuristics. We encourage it to prioritize moves that make use of tiles whose
    removals expose new tiles. We do this by considering features such as the
    position of the tile and the availabilities of the neighboring tiles. A
    value is assigned to each feature, and the values are weighted to calculated
    to final score of a move. The weights are tuned by hand, but if we had time
    we could use techniques such as temporal-difference learning or neural
    networks. At the end, the move with the highest score is selected.

    The cheating AI player attempts to do an $A^*$ search over the space of
    possible moves, using the above heuristics for move ordering. As expected,
    a complete search is not feasible for this game, and a bounded depth search
    didn't really work for us, because once we reached a given depth, we still
    don't know whether a board is ``good'' or not so we cannot decide whether
    we should take the initial move of the search path. What we implemented is
    then a modified search. We play the board ten times, in the $i$-th round,
    we always use the the $i$-th best move according to our heuristic. If we
    cannot solve the board in ten iterations, then we pick a random move. As
    shown in the diagrams below, it tends to work well in practice, at least
    for the two test layout used.

    We introduced a fourth AI, which is a Monte Carlo player. It can be invoked
    for the batch mode by providing \textsf{montecarlo} as the AI option. It
    keeps on playing the same board randomly again and again, until it solves
    the board or the limit of 1000 iteration is reached, in the latter case it
    just chooses a move at random. This gives very good winning percentages as
    shown below, mainly because a random player solves a solvable board roughly
    $25\%$ of the time and solves a random board roughly $5\%$ of the time.
    However, we should note that the results are only from the Turtle layout
    and the Ziggurat layout. There can be layouts in which the Monte Carlo
    player performs poorly.

  \item[Results]\hfill\\
    Here is the result of running different combinations of AI's, layouts and
    boards (solvable or random) with 1000 repetitions:

    \begin{centering}
      \begin{tabular}{|c|c|c|c|c|}
        \hline
        AI  & Solvable Turtle & Random Turtle & Solvable Ziggurat & Random Ziggurat
        \\\hline
        Random      & 250  & 51  & 237  & 33  \\\hline
        Heuristic   & 585  & 127 & 509  & 296 \\\hline
        Cheating    & 985  & 574 & 985  & 798 \\\hline
        Monte Carlo & 1000 & 817 & 1000 & 939 \\\hline
      \end{tabular}
    \end{centering}
    \\[1cm]

    \hspace{-1cm}
    \includegraphics[scale=0.4]{solvableTurtle.pdf}
    \includegraphics[scale=0.4]{randomTurtle.pdf}
    \\[1cm]

    \hspace{-1cm}
    \includegraphics[scale=0.4]{solvableZiggurat.pdf}
    \includegraphics[scale=0.4]{randomZiggurat.pdf}

  \item[Contributions]\hfill\\
    Gary Roumanis implemented the cheating player, redesign the GUI and
    implemented the user interface for AI playing.

    Andrew Sutcliffe implemented the random player and the heuristic player
    with the heuristics. He also provided the unit tests.

    Shen Chen Xu implemented the Monte Carlo player and the batch mode. He also
    prepared this report.

\end{description}
\end{document}
